A Pumping Lemma for Two-Way Finite Transducers

Notes

* [2019 May 24] Olivier Gauwin has brought to my attention the prior work of Brigitte Rozoy, who proved a similar pumping lemma in "Outils et résultats pour les transducteurs boustrophédons", published in RAIRO - Informatique théorique et applications in 1986.

Errata

The errors below are present in the conference publication, but have been fixed in the latest version available here.

Section 5 (Application)

* [2014 Aug 12] In the proof of Theorem 2, replace {w,u,z,h,a,o} with {w,u,z,h,a,o}^* and replace {a,b} with {a,b}^*.